/**
 * 快速排序
 */
pub fn quick_sort<T: Ord + Clone>(arr: &[T]) -> Vec<T> {
    let mut arr = Vec::from(arr);
    let len = arr.len();
    if len > 1 {
        _quick_sort(&mut arr, 0, len - 1);
    }
    arr
}

fn _quick_sort<T: Ord>(arr: &mut Vec<T>, low: usize, high: usize) {
    if low < high {
        let pivot = partition(arr, low, high);
        if pivot > 0 {
            _quick_sort(arr, low, pivot - 1);
        }
        _quick_sort(arr, pivot + 1, high);
    }
}

fn partition<T: Ord>(arr: &mut [T], low: usize, high: usize) -> usize {
    let mid = low + (high - low) / 2;
    if arr[low] > arr[high] {
        arr.swap(low, high);
    }
    if arr[mid] > arr[high] {
        arr.swap(mid, high);
    }
    if arr[mid] > arr[low] {
        arr.swap(mid, low);
    }

    let mut left = low + 1;
    let mut right = high;
    loop {
        while left <= right && arr[left] <= arr[low] {
            left += 1;
        }
        while left <= right && arr[right] >= arr[low] {
            right -= 1;
        }
        if left <= right {
            arr.swap(left, right);
        } else {
            break;
        }
    }
    arr.swap(low, right);
    right
}
